1. Technical Field
The present invention relates generally to machine recognition of handwritten text and, more particularly, to system and methods for preparing and organizing unconstrained handwriting data for machine recognition, and for arranging and formatting the resulting recognition results for display or subsequent post-processing.
2. Description of Related Art
When machine recognition is utilized to transcribe dynamically-recorded handwritten text into useful recognition results (e.g. fonted text, machine commands, database entries, etc.) the recognition results should reflect the intended meaning or purpose of the writer. For example, a horizontal dash through a vertical line must imply the crossing of a xe2x80x9ctxe2x80x9d and not a hyphen, whereas a table entry must not be formatted to appear as part of a grammatical sentence. In this respect, it is required that recorded series of handwritten strokes (i.e., electronic ink) be suitably organized and arranged for correct recognition, and in many cases, that the output recognition results be appropriately formatted for presentation.
In particular, prior to or concurrently with recognition, the recorded handwritten strokes should be organized such that the strokes are properly grouped and sequenced into letters, words or phrases as they are input to the recognizer. For certain handwriting recording devices, this may be a relatively simple task if the words are entered letter-by-letter, word-by-word, in the same order as they would be read. Such is the case with many real-time handwriting recording and recognition devices (e.g. Apple Newton, Palm Pilot), where the recognition results are strictly dependent on the (time) order in which the recorded handwriting strokes are entered.
When handwriting is recorded in an unconstrained manner, the writer may freely append and insert text anywhere on the handwriting recording surface and in any order so as to e.g., add text, tables, dates, punctuation, corrections, etc. This is typical of a handwriting recording device known as a personal digital notepad (PDN) device. The PDN device includes an electronic stylus having an inking tip which allows the user to write on a piece of paper placed over the digitizing tablet. As the writer writes on the paper, the digitizing tablet generates positional data representing the coordinates of the electronic stylus in relation to the digitizing tablet by detecting, for example, RF (radio frequency) signal emissions generated by the stylus as a user applies the stylus to the surface of the tablet. For each handwritten page, the PDN device may store a corresponding digital page that contains a time-ordered list of xe2x80x9cstrokesxe2x80x9d. The term xe2x80x9cstrokexe2x80x9d as used herein refers to a series of x-y coordinates recorded by the PDN device between the time the electronic pen is detected to contact the writing surface (i.e., a xe2x80x9cpen downxe2x80x9d signal) and the time the electronic pen is detected to move away from the writing surface (i.e., xe2x80x9ca pen-upxe2x80x9d signal). With this device, the writer can write one or two paragraphs, for example, and then go back and cross the xe2x80x9ctxe2x80x9d and dot the xe2x80x9cixe2x80x9d handwritten characters, thereby resulting in words having strokes that are not temporally adjacent (although spatially proximate).
Many of the currently available unconstrained handwriting recognition systems attempt to recognize such unconstrained handwriting data in the recorded or temporal sequence at which the handwriting data was recorded. If the user does not write in a disciplined, left-to-right, top-to-bottom order, for example, the decoding accuracy may be compromised. Therefore, in order to obtain increased decoding accuracy of such recorded unconstrained handwriting data, the recognition system should pre-process the handwriting data by appropriately segmenting, grouping and re-sequencing such recorded handwriting data before recognition.
Furthermore, the manner in which the recognition results from the recognizer are formatted is dependent on the environment. In some cases formatting is easy. For example, on many PDAs (e.g. the Newton, the Palm Pilot, etc.), the assumption made is that real-time input can be correctly handled by a typewriter analogy. The user""s ink is recognized when written and placed wherever the cursor is on the screen. The ink does not persist after it is recognized, so its original location does not imply or impart any particular meaning or content.
In other situations, such as with PDNs where the ink is written on a larger surface or a piece of paper, the formatting of the recognition results should xe2x80x9cmirrorxe2x80x9d the handwritten ink on the paper as faithfully as possible. This formatting is relatively straightforward when the ink is written to fill in a form which has fields such as name and date in pre-specified and well defined locations. Formatting is very difficult, however, for unconstrained handwriting since the formatting of the structure is not known beforehand. Poor formatting may make the recognition results difficult to read and difficult to use with word processors and other computer applications. In addition, it can lead to a perceived increase in the recognition error rate (e.g. words which are recognized correctly but put in the wrong order may appear to have been misrecognized.) Unfortunately, unconstrained handwriting recognition systems typically use temporal ordering to format recognition results. This leads to numerous problems which degrade perceived recognition accuracy (e.g. spatial information except for carriage returns is ignored leading to numerous out of order sentences, lists, dates, etc.).
The present application is directed to systems and methods for reordering unconstrained handwriting data using both spatial and temporal interrelationships prior to recognition, and for spatially organizing and formatting machine recognized transcription results. The present invention allows a machine recognizer to generate and present a full and accurate transcription of unconstrained handwriting in its correct spatial context (i.e., the transcription output can appear to xe2x80x9cmirrorxe2x80x9d the corresponding handwriting).
In one aspect, a handwriting recognition system comprises:
means for storing handwriting data, the handwriting data comprising a set of strokes, each stroke comprising a set of x-y coordinates;
a recognition engine; and
a system for spatially sorting handwriting data for recognition, the spatial sorting system comprising:
means for determining bounding region information for each stroke based on the x-y coordinates of the stroke;
means for clustering the strokes into groups of spatially-related strokes based on the bounding region information; and
means for ordering the clustered groups; and
means for submitting the ordered clustered groups to the recognition engine.
In another aspect, the handwriting recognition system further comprises a system for spatially formatting recognition results from the recognition engine, the spatial formatting system comprising means for positioning the recognized text on a display page in a proximate spatial location as the corresponding handwriting data is located on an ink page using the bounding region information for the corresponding handwriting data.
In yet another aspect, the handwriting recognition system further comprises:
means for tracking a recognition state comprising previous recognition results for each stored page of handwriting data; and
means for merging current recognition results from the recognition engine with a corresponding recognition state to produce the recognition results that are processed by the spatial formatting system.
These and other aspects, features and advantages of the present invention will be described and become apparent from the following detailed description of preferred embodiments, which is to be read in connection with the accompanying drawings.